#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
const int S = 5e5+10;
vector<int> bian[S];
int dfn[S];
int siz[S];
int top[S];
int son[S];
int dep[S];
struct ACAM{
    int to[S][4];
    int fail[S];
    int rot;
    int pcnt;
    int gen(){
        int now = ++pcnt;
        memset(to[now],0,sizeof(to[now]));
        fail[now] = 0;
        return now;
    }
    void init(){
        rot = gen();
    }
    int insert(string s){
        int now = gen();
        for(char c : s){
            c -= 'a';
            if(!to[now][c]){
                to[now][c] = gen();
            }
            now = to[now][c];
        }
        return now;
    }
    void build(){
        queue<int> que;
        for(int i = 0;i < 4;i++){
            if(to[rot][i]){
                que.push(to[rot][i]);
                fail[to[rot][i]] = rot;
            }else{
                to[rot][i] = rot;
            }
        }
        while(que.size()){
            int now = que.front();
            que.pop();
            bian[fail[now]].push_back(now);
            for(int i = 0;i < 4;i++){
                if(to[now][i]){
                    que.push(to[now][i]);
                    fail[to[now][i]] = to[fail[now]][i];
                }else{
                    to[now][i] = to[fail[now]][i];
                }
            }
        }
    }
} acam;
int fath[N];
void dfs1(int x,int fa){
    siz[x] = 1;
    fath[x] = fa;
    for(int v: bian[x])
    {
        dfs1(v,x);
        siz[x] += siz[v];
        if(siz[v] > siz[son[x]]){
            son[x] = v;
        }
    }
}
void dfs2(int x,int tf){
    top[x] = tf;
    if(son[x]){
        dfs2(son[x],tf);
    }
    for(int v: bian[x]){
        if(v == son[x]){
            continue;
        }
        dfs2(v,v);
    }
}
int lca(int u,int v){
    while(top[u] != top[v]){
        if(dep[top[u]] < dep[top[v]]){
            swap(u,v);
        }
        u = fath[top[u]];
    }
    if(dep[u] > dep[v]){
        swap(u,v);
    }
    return u;
}
string s[N];
string t[N];
int St[S],sp;
vector<int> bian1[S];
void bvt(const vector<int> &val){
    sp = 0;
    St[++sp] = 1;
    bian1[1].clear();
    for(int i = val.front() == 1;i < val.size();i++){
        int lc = lca(St[sp],val[i]);
        if(lc != St[sp]){
            while(dfn[St[sp - 1]] > lc){
                bian1[St[sp - 1]].push_back(St[sp]);
                sp--;
            }
            if(St[sp - 1] != lc){
                bian1[lc].clear();
                bian1[lc].push_back(St[sp]);
                St[sp] = lc;
            }else{
                bian1[lc].push_back(St[sp]);
                sp--;
            }
        }
        bian1[val[i]].clear();
        St[++sp] = val[i];
    }
    while(sp > 1){
        bian1[St[sp - 1]].push_back(St[sp]);
        sp--;
    }
}

const int V = 1e3+10;
struct segment_tree{
    int ls[V*30];
    int rs[V*30];
    long long sum[V*30];
    int pcnt;
    void update(int &now,int cop,int l,int r,int p,int v){
        now = ++pcnt;
        ls[now] = ls[cop];
        rs[now] = rs[cop];
        sum[now] = sum[cop] + v;
        if(l == r){
            return;
        }
        int mid = (l + r)/2;
        if(p <= mid){
            update(ls[now],ls[now],l,mid,p,v);
        }else
        {
            update(rs[now],rs[now],mid+1,r,p,v);
        }
    }
    long long query(int now,int l,int r,int x,int y){
        if(x <= l && r <= y){
            return sum[now];
        }
        int mid = (l + r)/2;
        long long res = 0;
        if(x <= mid){
            res += query(ls[now],l,mid,x,y);
        }
        if(mid < y){
            res += query(rs[now],mid+1,r,x,y);
        }
        return res;
    }
}sg;
int id[S];
int v[N];
int rot[N];
int ma;
void dfs4(int x,int fa){
    rot[x] = rot[fa];
    if(id[x]){
        sg.update(rot[x],rot[x],1,ma,v[id[x]],1);
    }
    for(int v : bian[x]){
        dfs4(v,x);
    }
}
int ml;
int cnt[S];
int dfs3(int x,int fa,long long lmt){
    int res = 0;
    for(int v : bian1[x]){
        res += dfs3(v,x,lmt);
        cnt[x] += cnt[v];
    }
    int ge =  (lmt + cnt[x] - 1)/cnt[x];
    if(ge <= ma){
        res += sg.query(rot[x],1,ma,ge,ma) - sg.query(rot[fa],1,ma,ge,ma);
    }
    return res;
}
int main(){
    int n,m;
    cin>>n>>m;
    acam.init();
    ma = 0;
    for(int i = 1;i<=n;i++){
        cin>>s[i];
        id[acam.insert(s[i])] = i;
        cin>>v[i];
        ma = max(ma,v[i]);
    }
    acam.build();
    dfs1(acam.rot,0);
    dfs2(acam.rot,acam.rot);
    dfs4(acam.rot,0);
    for(int i = 1;i<=m;i++){
        cin>>t[i];
        int k;
        cin>>k;
        int cur = acam.rot;
        vector<int> nds;
        for(char c: t[i]){
            cur = acam.to[cur][c - 'a'];
            nds.push_back(cur);
        }
        sort(nds.begin(),nds.end(),[](int x,int y){
            return dfn[x] < dfn[y];
        });
        for(int v: nds){
            cnt[v]++;
        }
        nds.erase(unique(nds.begin(),nds.end()),nds.end());
        bvt(nds);
        long long l = 1,r = 1e14;
        long long res = 0;
        while(l <= r){
            long long mid = (l + r)/2;
            if(dfs3(1,0,mid) >= k){
                res = mid;
                l = mid + 1;
            }else{
                r = mid - 1;
            }
        }
        for(int v : nds){
            cnt[v] = 0;
        }
        cout<<res<<'\n';
    }
}